package com.fps.webshop.question.question0001_0099;

import java.util.*;

/**
 * 15. 三数之和
 * 
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
 * 请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 * 示例 1：
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 *
 * 示例 2：
 * 输入：nums = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：nums = [0]
 * 输出：[]
 *
 * 提示：
 * 		0 <= nums.length <= 3000
 * 		-10^5 <= nums[i] <= 10^5
 *
 */
public class Question015 {

	/**
	 * 第一次提交，三层循环暴力破解，大概率没问题，但是超出时间限制，无法验证
	 * 提交结果		执行用时	内存消耗	语言		提交时间				备注
	 * 超出时间限制	N/A		N/A		Java	2021/09/06 16:34
	 */
	public static List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> allList = new ArrayList<>();
		if(nums==null||nums.length<3){
			return allList;
		}
		Set<String> set = new HashSet<>();
		for(int i=0;i<nums.length-2;i++){
			for(int j = i+1;j<nums.length-1;j++){
				for(int k = j+1;k<nums.length;k++){
					if(nums[i]+nums[j]+nums[k]==0){
						List<Integer> list = new ArrayList<>();
						int[] li = new int[3];
						li[0] = nums[i];
						li[1] = nums[j];
						li[2] = nums[k];
						Arrays.sort(li);
						set.add(li[0]+","+li[1]+","+li[2]);
					}
				}
			}
		}
		if(!set.isEmpty()){
			for(String str: set){
				String[] a = str.split(",");
				List<Integer> list = new ArrayList<>();
				list.add(Integer.parseInt(a[0]));
				list.add(Integer.parseInt(a[1]));
				list.add(Integer.parseInt(a[2]));
				allList.add(list);
			}
			return allList;
		}else{
			return allList;
		}
	}

	/**
	 * 第2次提交，官方解答，排序+双指针
	 *
	 * 提交结果		执行用时	内存消耗	语言		提交时间				备注
	 * 通过			20 ms	42.4 MB	Java	2021/09/07 13:58
	 *
	 * 执行用时：20 ms, 在所有 Java 提交中击败了89.92%的用户
	 * 内存消耗：42.4 MB, 在所有 Java 提交中击败了52.03%的用户
	 *
	 */
	public List<List<Integer>> threeSum2(int[] nums) {
		int n = nums.length;
		Arrays.sort(nums);
		List<List<Integer>> ans = new ArrayList<List<Integer>>();
		// 枚举 a
		for (int first = 0; first < n; ++first) {
			// 需要和上一次枚举的数不相同
			if (first > 0 && nums[first] == nums[first - 1]) {
				continue;
			}
			// c 对应的指针初始指向数组的最右端
			int third = n - 1;
			int target = -nums[first];
			// 枚举 b
			for (int second = first + 1; second < n; ++second) {
				// 需要和上一次枚举的数不相同
				if (second > first + 1 && nums[second] == nums[second - 1]) {
					continue;
				}
				// 需要保证 b 的指针在 c 的指针的左侧
				while (second < third && nums[second] + nums[third] > target) {
					--third;
				}
				// 如果指针重合，随着 b 后续的增加
				// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
				if (second == third) {
					break;
				}
				if (nums[second] + nums[third] == target) {
					List<Integer> list = new ArrayList<Integer>();
					list.add(nums[first]);
					list.add(nums[second]);
					list.add(nums[third]);
					ans.add(list);
				}
			}
		}
		return ans;
	}

	/**
	 * 第3次提交，网友解答，排序+双指针
	 *
	 * 提交结果		执行用时	内存消耗	语言		提交时间				备注
	 * 通过	20 ms	42.1 MB	Java	2021/09/07 13:59
	 *
	 * 执行用时：20 ms, 在所有 Java 提交中击败了89.92%的用户
	 * 内存消耗：42.1 MB, 在所有 Java 提交中击败了82.85%的用户
	 */
	public List<List<Integer>> threeSum3(int[] nums) {// 总时间复杂度：O(n^2)
		List<List<Integer>> ans = new ArrayList<>();
		if (nums == null || nums.length <= 2) return ans;

		Arrays.sort(nums); // O(nlogn)

		for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
			if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
			if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
			int target = -nums[i];
			int left = i + 1, right = nums.length - 1;
			while (left < right) {
				if (nums[left] + nums[right] == target) {
					ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));

					// 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
					left++; right--; // 首先无论如何先要进行加减操作
					while (left < right && nums[left] == nums[left - 1]) left++;
					while (left < right && nums[right] == nums[right + 1]) right--;
				} else if (nums[left] + nums[right] < target) {
					left++;
				} else {  // nums[left] + nums[right] > target
					right--;
				}
			}
		}
		return ans;
	}


	public static void main(String[] args) {
		int[] nums = new int[]{-1,0,1,2,-1,-4};
		List<List<Integer>> results = threeSum(nums);
		for(List<Integer> list :results){
			for(Integer a : list){
				System.out.print(a+" ");
			}
			System.out.println();
		}
	}
}
